package 插入排序;

import java.util.Arrays;

public class 插入排序 {

	public static void main(String[] args) {
//		int[] arr = {5, 4, 3, 2, 1 };
//		insertSort(arr);
//		System.out.println(Arrays.toString(arr));
		
		int[] longInt = new int[80000];
		for (int i = 0; i < longInt.length; i++) {
			longInt[i] = (int) (Math.random()*10000);
		}
		
		long star = System.currentTimeMillis();
		insertSort(longInt);
		long end = System.currentTimeMillis();
		System.out.println((end-star) + "毫秒");
		System.out.println((end-star)/1000 + "秒");//2s

	}

	/**
	 * 插入排序
	 * @param arr
	 */
	public static void insertSort(int[] arr) {

		int value = 0;
		int index = 0;

		for (int i = 1; i < arr.length; i++) {
			// 当前循环的值
			value = arr[i];
			// 当前值的前一个值下标，已排序数组最后一个
			index = i-1;

			// 如果当前数大于前一个数，就不用交换，因为前面已经排好序，最后一个一定最大，既然大于最大值
			// 就可以直接跟在后面了
			// 小于前一个数才进入，不要忘记 if 怎么用的，成立才进入，不成立不进入
			if (arr[i] < arr[index]) {

				//当前值小于前一个值，说明前一个大，就把大的那个赋给小的，这两个变成大的了，
				//例如 2,3,5,4 ==> 2,3,5,5   此时value还保存着当前值 1，用于对比找到合适位置
				while(index >= 0 && value < arr[index]) {
					//当前值 = 前一个值
					arr[index+1] = arr[index];
					//回到前一个的前一个，下次再对比，注意：因为是先 减减 再 对比，所以提前了一步
					index--;
				}
				//一直找到第合适位置的前一个 提前了一步，所以 +1
				//例如 2,3,5,5 ==> 2,3,4,5
				arr[index+1] = value;

			}
		}

		//一样的方式，只不过从 value = index 是一个数的值和下标，后面用index - 1 ，和for
		/*for (int i = 1; i < arr.length; i++) {
			// 当前循环的值
			 value = arr[i];
			// 当前值的下标
			 index = i;

			// 如果当前数大于前一个数，就不用交换，因为前面已经排好序，最后一个一定最大，既然大于最大值
			// 就可以直接跟在后面了
			if (arr[i] < arr[index-1]) {

				// 如果当前值小于前一个，就将这两个都变成大的那一个值 2,3,4,1==>2,3,4,4
				for (; index >= 1 && value < arr[index-1]; index--) {
					 arr[index] = arr[index - 1];
				}
				arr[index] = value;
			}
		}*/

	}
}
